package hashtable.intersection;

/**
 * 题目:
   给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 * 示例 2：
   输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
   输出：[9,4]
   解释：[4,9] 也是可通过的
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 暴力法(自己解)
 * class Solution {
 *     public int[] intersection(int[] nums1, int[] nums2) {
 *         ArrayList<Integer> res=new ArrayList<>();
 *         for(int i=0;i<nums1.length;i++){
 *             for(int j=0;j<nums2.length;j++){
 *                 if(nums1[i]==nums2[j]){
 *                     // 检查是否已经存在于结果中，避免重复
 *                     if (!res.contains(nums1[i])){
 *                         res.add(nums1[i]);}
 *                     break;
 *                 }
 *             }
 *         }
 *         // 转换为 int[]
 *         int[] result = new int[res.size()];
 *         for (int i = 0; i < res.size(); i++) {
 *             result[i] = res.get(i);
 *         }
 *         return result;
 *     }
 * }
 */


//如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
//此时使用set更好
//将nums1转为hashset,用nums2判断是否存在
public class Intersection {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set1=new HashSet<>();
        Set<Integer> res=new HashSet<>();

        //遍历数组1
        for(int i:nums1){
            set1.add(i);
        }

        //遍历数组2的过程中判断哈希表中是否存在该元素
        for(int i: nums2){
            if(set1.contains(i)){
                res.add(i);
            }
        }

        //返回数组
        int[] arr=new int[res.size()];
        int j=0;
        for(int i:res){
            arr[j++]=i;
        }

        return arr;

    }
}
